package Test;

public class 最大子数组和 {
    public static void maxSubArray(int[] nums) {
        int [] dp=new int[nums.length];
        dp[0]=nums[0];
        for (int i=1;i<nums.length;i++){
            dp[i]=Math.max(nums[i],dp[i-1]+nums[i]);
        }
        int res=0;
        for (int i:dp){
            res=Math.max(i,res);
        }
        System.out.println(res);
    }

    /*************环形数组**************/
    public static int maxSubarraySumCircular(int[] nums) {
        int n=nums.length;
        int []maxdp=new int[n];
        int []mindp=new int[n];
        maxdp[0]=nums[0];
        mindp[0]=nums[0];
        int sum=nums[0];
        for (int i=1;i<n;i++){
            maxdp[i]=Math.max(nums[i],maxdp[i-1]+nums[i]);
            mindp[i]=Math.min(nums[i],mindp[i-1]+nums[i]);
            sum+=nums[i];
        }
        int max=Integer.MIN_VALUE;
        int min=Integer.MAX_VALUE;
        for (int i:maxdp){
            max=Math.max(i,max);
        }
        for(int i:mindp){
            min=Math.min(min,i);
        }
        return Math.max(max,sum-min==0?max:sum-min);
    }

    public static void main(String[] args) {
        int[] arr={5,-3,5};
        System.out.println("maxSubarraySumCircular(arr) = " + maxSubarraySumCircular(arr));
    }
}
